// https://leetcode.cn/problems/reorganize-string/description/

// 算法思路总结：
// 1. 贪心策略重构字符串避免相邻重复
// 2. 统计字符频率并找到最高频字符
// 3. 先间隔放置最高频字符确保不冲突
// 4. 剩余字符填充空位检查可行性
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <algorithm>

class Solution 
{
public:
    string reorganizeString(string s) 
    {
        int m = s.size();
        string res(m, 'a');
        unordered_map<char, int> hash;

        int maxCount = 0; char maxChar;
        for (const char& ch : s)
        {
            if (maxCount < ++hash[ch])
            {
                maxCount = hash[ch];
                maxChar = ch;
            }
        }

        int index = 0;
        for (int i = 0 ; i < maxCount ; i++)
        {
            if (index >= m)
            {
                return "";
            }
            res[index] = maxChar;
            index += 2;
        }
        
        hash.erase(maxChar);
        for (auto& [x, y] : hash)
        {
            for (int i = 0 ; i < y ; i++)
            {
                if (index >= m) 
                {
                    index = 1;
                }
                res[index] = x;
                index += 2;
            }
        }

        return res;
    }
};

int main()
{
    string s1 = "aab", s2 = "aaab";
    Solution sol;

    cout << sol.reorganizeString(s1) << endl;
    cout << sol.reorganizeString(s2) << endl;

    return 0;
}